This invention relates to a system for relative vehicle navigation, and particularly relates to such a system for use in underground passageways or tunnels, for instance, an underground mine, and to control the movement of vehicles.
The invention will be described with reference to remotely operated mining vehicles in an underground mine, but it should be appreciated that the invention need not be limited to this embodiment.
The underground mining environment is unstructured in a robotic sense but is topologically highly structured. It consists of well-defined paths (tunnels with walls), intersections, muck piles and ore passes.
The navigation of a vehicle in such an environment can be compared to the task of rally driving, where the navigation of the vehicle is shared between driver and navigator. The driver is concerned simply with moving the vehicle forward and staying on the road, whilst the navigator uses pace notes to sequence his/her attention for landmarks, and provide instructions to the driver about the path to take at intersections.
In order to drive successfully, there is no need for precise absolute location data. The only time the location of the vehicle is needed is at intersections where a decision must be made. Fortunately, the very nature of these intersections make them easy to identify (coupled with odometry data and expectations from the map) and it is possible to reliably determine the position of the vehicle with respect to the intersection geometry.
The advantage to this approach is that it is very tolerant to: changes within the environment; machine performance, i.e. changes to tires and weight; and imprecise initialisation and map building. The interaction between the driver and navigator is shown in FIG. 1.
Traditional navigation systems are based upon an absolute frame of reference where the position of the vehicle is defined in terms of the distance with respect to an external frame of reference. This system will be referred to as the Absolute Navigation System (ANS).
In many situations, where the path of the vehicle is constrained by a wall, a far more suitable approach is a navigation system based upon a relative frame of reference. This system will be referred to as the Relative Navigation System (RNS). FIG. 2 illustrates the main difference between the ANS and the RNS.
In the ANS there is a predetermined path, in terms of the external coordinate system, for the vehicle to follow. If the vehicle strays from the path (by some offset) then a local path correction is applied to the vehicle. In the RNS, there is no predefined path, only some distant destination. The desired path of the vehicle is a local path that is generated to keep the vehicle from hitting the walls. Although these systems may generate a similar xe2x80x9cvehicle pathxe2x80x9d the control systems used to generate these paths are quite different.
FIG. 3 illustrates vehicle control using the ANS. This system requires a map and a global-path. The map contains the position of landmarks used to help establish the location of the vehicle. Localisation is achieved by comparing the landmarks in the mine-map with data from position sensors (e.g. the position of reflective beacons) and fusing this information with dead reckoning. The position sensors can be reflective beacons which need to be placed at known positions in the mine. The global-path is a set of points, with respect to the external coordinate frame, that define a predetermined path through the mine. Local path planning is achieved by comparing where we are (x,y) with where we should be (xxe2x80x2,yxe2x80x2). This tells us where we want to go. The correction (dx,dy) is fed into a kinematic model, which is coupled with the state of the vehicle (velocity, acceleration) to estimate a change in heading (dxcex1) and speed (dv).
The ANS is effectively blindxe2x80x94the control of the vehicle is inferred from the position of the vehicle, rather than what the sensors tell it about the environment. If there is any error in the localisation then it is quite possible for the vehicle to collide with a wall.
It is an object of the present invention to provide a means to guide a vehicle in an underground environment which does not rely upon an ANS.
In one form, the invention resides in a means of navigating (IEEE Dictionary: xe2x80x9cThe process of driving a vehicle so as to reach the intended destinationxe2x80x9d), without localisation infrastructure (this refers to infrastructure that is added to the external environment to help localise the vehicle; it can include active and passive beacons) or external control, an autonomous vehicle along a path that is confined by walls (the wall does not need to be real; it can be conceptualxe2x80x94it is simply a boundary between where the vehicle can and cannot go) that are within range of on-board sensors by determining the relative location and orientation of the walls with respect to the vehicle, the means comprising:
Means of controlling the vehicle (setting steer angle and ground speed) without localisation comprising hardware and means to:
(a) use range data to establish free space in front of vehicle,
(b) use active contours (or snakes) to generate a desired path,
(c) use driving hints to guide the or a said snake, for instance along arcs and open areas, and/or to
(d) use steering hints to confine the snake to a specific domain of free space, for instance at intersections, and
(e) use desired path to generate steering demand and velocity.
In a broad form, the invention resides in a method for navigating a vehicle, the method comprising creating active contours (or snakes) to generate a desired path for the vehicle, using driving hints to guide the or a said snake and/or using steering hints to confine the snake to a specific domain of free space.
The range data may be generated from on-board sensors which emit and receive electro-magnetic/ultra-sonic radiation to determine the range and bearing of walls.
The active contours to generate the desired path may be such that:
i. the desired path must avoid walls and preferably minimise curvature.
ii. the length and stiffness of the snake is a function of the vehicle and its state.
iii. the xe2x80x9cenergyxe2x80x9d of the snake is a defined function of the proximity to walls and its curvature.
iv. if the xe2x80x9cenergyxe2x80x9d exceeds a predefined limit, the velocity of vehicle is reduced and if the xe2x80x9cenergyxe2x80x9d continues to exceed the limit for predetermined time/distance the vehicle is stopped.
The driving hints to guide the snake along arcs and open areas may:
i. modify speed according to local curvature and recommended speed limits.
ii. add a xe2x80x9cpotential gradient energyxe2x80x9d term to bias the position of the snake (i.e. keep left).
The steering hints to guide the snake may be such that:
i. radial rails are generated in front of the vehicle,
ii. the rails are segmented into bands by the topology of the free space,
iii. appropriate bands are selected by steering hints, and
iv. snake vertices are fitted to selected bands.
The desired path to generate steering demand and velocity may compare radius of curvature of vehicle, with radius of curvature of path.
In another form, the invention resides in a means of localising the vehicle without localisation infrastructure comprising:
(a) a means of establishing the or a starting position,
(b) using dead-reckoning (ground speed, INS etc) to estimate the vehicle position,
(c) using range data to find topology of free space in front of vehicle,
(d) identifying changes in topology as landmarks (nodes),
(e) matching said nodes to nodal-map to update vehicle position,
(f) using knowledge of position and nodal-map to pass driving hints to vehicle control,
(g) using knowledge of position and nodal-path to pass steering hints to vehicle control.
The dead-reckoning may be such that:
i. vehicle position is defined as the approximate distance to the next node.
ii. vehicle position is reset once a node has been passed.
The range data to find topology of free space in front of vehicle may be such to:
i. offset and re-scale data to front centre of vehicle.
ii. smooth and re-sample range data.
iii. generate contour of equally spaced points.
The identification of changes in topology as landmarks (nodes) may comprise:
i. skeletonising free space.
ii. pruning branches that are insignificant.
iii. label remaining intersections as nodes.
The matching of these nodes to nodal-map to update vehicle position may comprise:
i. ignoring nodes that are not expected (from nodal-map and position).
ii. matching based upon minimum radius, energy, and connectivity.
The use of knowledge of position and nodal-map to pass driving hints to vehicle control may include, max-speed, gradient, curvature and wall profile.
The use of knowledge of position and nodal-path to pass steering hints to vehicle control may include:
i. the nodal-path containing a list of nodes that the vehicle must pass through; and
ii. the steering hints consisting of turn-left, turn-right, stop, etc.
In another form, the invention resides in the creation of a nodal-map that contains:
(a) position of landmarks (topological nodes, intersections).
(b) topological relationship between nodes (distance, curvature, etc).
(c) the nature of the arc that connects the nodes (driving hints).
(d) a means where a nodal-map of the intended path and features is determined by driving the vehicle along the intended path, logging and processing the data obtained from all or any of the aforementioned sensors and storing the nodal-map along with the identifying characteristics of the nodes in memory.
The nature of the arc that connects the nodes may be such to:
i. account for physical limitations (i.e. gradient).
ii. to improve the performance of the vehicle.
iii. to account for unusual/dangerous conditions, i.e. wall-profile.
iv. such hints will depend on the direction of travel.
The means where a nodal-map of the intended path and features is determined by driving the vehicle along the intended path, logging and processing the data obtained from all or any of the aforementioned sensors and storing the nodal-map along with the identifying characteristics of the nodes in memory may comprise:
i. A means where the dead-reckoning method is used to estimate the relative position of the nodes along the intended track in either the forward or reverse direction with respect to the vehicle.
ii. A means where the range finding data is used generate a representation of the tunnel walls in the mine.